package leetcode_100;

import java.util.Arrays;

public class FindFirstAndLastPositionOfElementInSortedArray_34 {
	public static void main(String[] args) {
		FindFirstAndLastPositionOfElementInSortedArray_34 test=new FindFirstAndLastPositionOfElementInSortedArray_34();
		test.searchRange1(new int[] {5,7,7,8,8,10}, 8);
	}
	
	/**
	 * describe:单二分 然后扩散 AC 24%
	 * 2018年12月24日 下午7:11:27
	 */
	public int[] searchRange(int[] nums, int target) {
		if(nums.length==0) return new int[] {-1,-1};
		int index=Arrays.binarySearch(nums, target);
		if(index<0) return new int[] {-1,-1};
		int left=index,right=index;
		while(left>=0&&nums[left]==target) --left;
		while(right<nums.length&&nums[right]==target) ++right;
		return new int[] {left+1,right-1};
	}
	
	/**
	 * describe:双二分 AC 24%
	 * 2018年12月24日 下午7:47:21
	 */
	public int[] searchRange1(int[] nums, int target) {
		if(nums.length==0) return new int[] {-1,-1};
		int left=0,right=nums.length-1,mid;
		int res[]=new int[2];
		while(left<right) {
			mid=left+((right-left)>>1);
			if(nums[mid]>target) {
				right=mid-1;
			}
			else if(nums[mid]<target)
				left=mid+1;
			else {
				if(left+1==right&&nums[left]==target&&nums[right]==target) {
					right=left;
					break;
				}
				right=mid;
			}
		}
		if(nums[left]!=target) return new int[] {-1,-1};
		res[0]=right;
		left=0;
		right=nums.length-1;
		while(left<right) {
			mid=left+((right-left+1)>>1);
			if(nums[mid]<target) {
				left=mid+1;
			}
			else if(nums[mid]>target)
				right=mid-1;
			else {
				if(left+1==right) {//这是死循环的入口 因为取的是mid就是left
					if(nums[left]==target&&nums[right]==target) {
						left=right;
						break;
					}
				}
				left=mid;
			}
		}
		res[1]=left;
		return res;
	}
}
